Frame partitioning is a process of key importance in efficient video coding. Most of the current video compression technologies use tree based frame partitioning. One exemplary current video compression technology involves the International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) Moving Picture Experts Group-4 (MPEG-4) Part 10 Advanced Video Coding (AVC) standard/International Telecommunication Union, Telecommunication Sector (ITU-T) H.264 Recommendation (hereinafter the “MPEG-4 AVC Standard”). The frame partition in the MPEG-4 AVC Standard is more efficient than a simple uniform block partition, the latter typically used in older video coding standards such as MPEG-2. However, tree based frame partitioning still does not code video information efficiently enough, as it is unable to capture the geometric structure of two-dimensional (2D) data.
While geometry-adaptive block partitioning has been proposed to improve the coding efficiency, it does so at the cost of complexity. To obtain improved performance, a first prior art approach supports all the partition modes based on each distance and angle. In the first prior art approach, a simple adaptive model for partitioning a block is used. In further detail, a straight line model is used to adapt an angle and location in order to capture the local geometrical statistical dependence of predictable regions. Line coding is performed by sending two indexes. Each one of these two indexes corresponds to a value of the angle and distance to the center of the block. A quantization step for the distance Δρ and the angle Δθ can be fixed on a high syntax level in order to have the best rate-distortion (R-D) compromise in the bits spent for coding the partition (as well as, if necessary, a control on the maximum allowed computational complexity).
A second prior art approach tries to reduce the partition mode complexity by limiting the angle Δθ to vertical, horizontal or diagonal (+45 degree or −45 degree) orientations. However, this degrades performance when compared to the first prior art approach.
In order to solve such limitations, the first prior art approach presents a method to better represent and code 2D video data by taking its 2D geometry into account. That is, the first prior art approach uses a wedge partition (i.e., a partition of a block in two regions that are separated by an arbitrary line or curve) for a new set of modes for both inter (INTER16×16GEO, INTER8×8GEO) and intra prediction (INTRA16×16GEO, INTRA8×8GEO).
Geometric partitions within blocks are modeled by the implicit formulation of a line. Hence, partitions are defined as follows:f(x,y)=x cos θ+y sin θ−ρ,where ρ and θ respectively represent: the distance from the origin to the boundary line f(x, y) in the orthogonal direction to f(x, y); and the angle of the orthogonal direction to f(x, y) with the horizontal coordinate axis x.
Each block pixel (x, y) is classified such that:
  GEO_Partition  =      {                                                      if              ⁢                                                          ⁢                              f                ⁡                                  (                                      x                    ,                    y                                    )                                                      >            0                                                Partition            ⁢                                                  ⁢            0                                                                          if              ⁢                                                          ⁢                              f                ⁡                                  (                                      x                    ,                    y                                    )                                                      =            0                                                Line            ⁢                                                  ⁢            Boundary                                                                          if              ⁢                                                          ⁢                              f                ⁡                                  (                                      x                    ,                    y                                    )                                                      <            0                                                Partition            ⁢                                                  ⁢            1                              
For coding purposes, a dictionary (a defined compilation or list) of possible geometric partitions (or geometric modes) is a priori defined. This can be formally defined by determining the value range and sampling precision for each parameter of f(x, y) as follows:
            ρ      ⁢              :            ⁢                          ⁢      ρ        ∈          [              0        ,                                            2                        ⁢                          MB              Size                                2                    )        and            ρ      ⋐              {                  0          ,                      Δ            ⁢                                                  ⁢            ρ                    ,                                    2              ·              Δ                        ⁢                                                  ⁢            ρ                    ,                                    3              ·              Δ                        ⁢                                                  ⁢            ρ                    ,          …                }              ,                  ⁢    and        θ    ⁢          :        ⁢                  ⁢          {                                                                                                                              if                      ⁢                                                                                          ⁢                      ρ                                        =                    0                                                                                        θ                    ∈                                          [                                              0                        ,                        180                                            )                                                                                                                    else                                                                      θ                    ∈                                          [                                              0                        ,                        360                                            )                                                                                            ⁢                                                  ⁢            and            ⁢                                                  ⁢            θ                    ⋐                      {                          0              ,                              Δ                ⁢                                                                  ⁢                θ                            ,                                                2                  ·                  Δ                                ⁢                                                                  ⁢                θ                            ,                                                3                  ·                  Δ                                ⁢                                                                  ⁢                θ                            ,              …                        }                          ,            where Δρ and Δθ are the selected quantization (parameter resolution) steps, and MBsize is the size of the macroblock. The quantized indices for θ and ρ are the information transmitted to code the partition boundary line. However, if modes 16×8 and 8×16 are used in the coding procedure, then angles 0 and 90, for the case of ρ=0, can be removed from the set of possible edges.
Within the embodiments presented in the first prior art approach, for geometry-adaptive motion compensation mode, a search on θ, ρ and motion vectors for each partition is performed in order to find the best configuration. A full search strategy is performed in two stages, such that for every θ, ρ pair, the best motion vectors are searched. Within the geometry-adaptive intra prediction mode, a search on θ, ρ and the best predictor (directional prediction, or statistics, etc.) for each partition is performed in order to find the best configuration.
At the encoder side, computational complexity for a geometric mode can be very high if a full search is used. At the decoder side, the decoder needs to support all the partition modes. If a lookup table is used to reduce on-the-fly computation of the mode shape, then the table will be very big.
Other geometric partition work described in the second prior art approach attempts to reduce the number of geometric modes by only allowing vertical, horizontal, or diagonal (+45 degree or −45 degree) orientations. This does decrease the complexity of the determination, but does so at the cost of degraded coding performance.